//lc第48题，顺时针90度旋转矩阵
#include <bits/stdc++.h>
using namespace std;
//顺时针旋转90度相当于先旋转矩阵，然后两两交换a[0,1...]和
//顺时针旋转90度相当于先旋转矩阵，然后两两交换a[0,1...]和
//class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[i].size();j++)
            {
                if(j>=i)swap(matrix[i][j],matrix[j][i]);
            }
        }
        for(int i=0;i<matrix.size();i++)
        {
            for(int x=0,y=matrix[i].size()-1;x<y;x++,y--)
            {
                swap(matrix[i][x],matrix[i][y]);
            }
        }
    }
};



//lc第50题，将属于同一个字符串的字母异位词分在一组
//方法1：不会移除，思路，用排序后的字符串做key，原字符串做value，
//方法2：字母异位词还是的每一个字符和原字符串还是一样的，可以用一个质数表或者自己统计每个字符出现的频率，做一下映射
//质数表测试用例比较多的时候会爆long long,换成double就可以
// class Solution {
// public:
//     vector<vector<string>> groupAnagrams(vector<string>& strs) {
//         unordered_map<string,vector<string>> mmap;
//         for(int i=0;i<strs.size();i++)
//         {
//             string temp=strs[i];
//             sort(temp.begin(),temp.end());
//             mmap[temp].push_back(strs[i]);
//         }
//         vector<vector<string>> ret;
//         for(auto& x:mmap)
//         {
//             ret.push_back(x.second);
//         }
//         return ret;
//     }
// };

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int primes[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                          31, 37, 41, 43, 47, 53, 59, 61,
                          67, 71, 73, 79, 83, 89, 97, 101};

        unordered_map<double,vector<string>> mmap;
        for(int i=0;i<strs.size();i++)
        {
            double key=1;
            for(char &s:strs[i])
            {
                key*=primes[s-'a'];
            }
            mmap[key].push_back(strs[i]);
        }
        vector<vector<string>> ret;
        for(auto &x:mmap)
        {
            ret.push_back(x.second);
        }
        return ret;
    }
};
